\newcommand{\mindegree}[0]{\delta}
\begin{algorithm}[]
\caption{\sc Pre-Processing($\eta$, $\lambda$)}
\label{alg:pre-processing}
\textbf{Input:} number of short walks of each node $v$ is $\eta deg(v)\log n$, and desired short walk lengths $\lambda$.\\
\textbf{Output:} set of short random walks of each nodes \\

\textbf{Each node $v$ performs $\eta_v=\eta \deg(v)\log n$
random walks of length $\lambda + r_i$ where $r_i$ (for each $1\leq
i\leq \eta$) is chosen independently at random in the range
$[0,\lambda-1]$.}
\begin{algorithmic}[1]
\STATE Let $r_{max} = \max_{1\leq i\leq \eta}{r_i}$, the random
numbers chosen independently for each of the $\eta_x$ walks.

\STATE Each node $x$ constructs $\eta_x$ messages containing its ID
and in addition, the $i$-th message contains the desired walk length
of $\lambda + r_i$.

\FOR{$i=1$ to $\lambda + r_{max}$}

\STATE Each node $v$ does the
following: Consider each message $M$ held by $v$ and received in the
$(i-1)$-th iteration (having current counter $i-1$). If the message
$M$'s desired walk length is at most $i$, then $v$ stored the ID of
the source ($v$ is the desired destination). Else, $v$ picks a
neighbor $u$ uniformly at random and forward $M$ to $u$ after
incrementing its counter.
%
%\COMMENT{Note that any iteration could require more than 1 round.}

\ENDFOR

\STATE Send the destination IDs back to the respective sources (this can be done
by sending the destination IDs along the "reverse" path).

\end{algorithmic}
\end{algorithm}


\begin{algorithm}[]
\caption{\sc Single-Random-Walk($s$, $\ell$)}
\label{alg:single-random-walk}
\textbf{Input:} Starting node $s$, and desired walk length $\ell$.\\
\textbf{Output:} Destination node of the walk outputs the ID of $s$.\\

\textbf{Stitch $\Theta(\ell/\lambda)$ walks, each of length in $[\lambda,2\lambda-1]$ }
\begin{algorithmic}[1]
\STATE The source node $s$ creates a message called ``token'' which
contains the ID of $s$

\STATE The algorithm generates a set of {\em connectors}, denoted by
$C$, as follows. (Connectors are the endpoints of the short walks, i.e., the points where we stitch.)

\STATE Initialize $C = \{s\}$

\WHILE {Length of walk completed is at most $\ell-2\lambda$}

  \STATE Let $v$ be the node that is currently holding the token.

  \STATE $v$ uniformly chooses one of its short length sample and let $v'$ be the
  sampled value if any exists (which is a destination of an unused random walk of length between $\lambda$ and $2\lambda-1$). 
%  Otherwise $v$ returns {\sc null}.

  \IF{$v' =$ {\sc null} (all walks from $v$ have already been used up)}

%  \STATE $v$ calls {\sc Get-More-Walks($v$, $\lambda$)} (Perform $\Theta(l/\lambda)$ walks
%  of length $\lambda$ starting at $v$) returned value

%  \STATE $v$ calls {\sc Sample-Destination($v$)} and let $v'$ be the
  
  \STATE Algorithm terminates failing this walk.

  \ENDIF

  \STATE $v$ sends the token to $v'$

  \STATE $C = C \cup \{v\}$

\ENDWHILE

\STATE Walk naively until $\ell$ steps are completed (this is at
most another $2\lambda$ steps)

\STATE A node holding the token outputs the ID of $s$

\end{algorithmic}

\end{algorithm}

%
%
%
\iffalse

\begin{algorithm}[t]
\caption{\sc Sample-Destination($v$)} \label{alg:sample-destination}
\textbf{Input:} Starting node $v$.\\
\textbf{Output:} A node sampled from among the stored
walks (of length in $[\lambda, 2\lambda-1]$) from $v$. \\

\textbf{Sweep 1: (Perform BFS tree)}
\begin{algorithmic}[1]

\STATE Construct a Breadth-First-Search (BFS) tree rooted at $v$.
While constructing, every node stores its parent's ID. Denote such
tree by $T$.

\end{algorithmic}

\textbf{Sweep 2: (Tokens travel up the tree, sample as you go)}
\begin{algorithmic}[1]

\STATE We divide $T$ naturally into levels $0$ through $D$ (where
nodes in level $D$ are leaf nodes and the root node $s$ is in level
$0$).

\STATE Tokens are held by nodes as a result of doing walks of length
between $\lambda$ and $2\lambda-1$ from $v$ (which is done in 
{\sc Pre-Processing}). A node could have more than one
token.

\STATE Every node $u$ that holds token(s) picks one token, denoted
by $d_0$, uniformly at random and lets $c_0$ denote the number of
tokens it has.

\FOR{$i=D$ down to $0$}

\STATE Every node $u$ in level $i$ that either receives token(s)
from children or possesses token(s) itself do the following.

\STATE Let $u$ have tokens $d_0, d_1, d_2, \ldots, d_q$, with counts
$c_0, c_1, c_2, \ldots, c_q$ (including its own tokens). The node
$v$ samples one of $d_0$ through $d_q$, with probabilities
proportional to the respective counts. That is, for any $1\leq j \leq
q$, $d_j$ is sampled with probability
$\frac{c_j}{c_0+c_1+\ldots+c_q}$.

\STATE The sampled token is sent to the parent node (unless already
at root), along with a count of $c_0+c_1+\ldots+c_q$ (the count
represents the number of tokens from which this token has been
sampled).

\ENDFOR

\STATE The root output the ID of the owner of the final sampled
token. Denote such node by $u_d$.

\end{algorithmic}

\textbf{Sweep 3: (Go and delete the sampled destination)}
\begin{algorithmic}[1]

\STATE $v$ sends a message to $u_d$ (e.g., via broadcasting). $u_d$
deletes one token of $v$ it is holding (so that this random walk of
length $\lambda$ is not reused/re-stitched).
\end{algorithmic}

\end{algorithm}

\fi
%
%
%


\begin{algorithm}[H]
\caption{\sc Continuous-Random-Walk($\ell$)} \label{alg:continuous-random-walk}
\textbf{Input:} $\ell$.\\
\textbf{Output:} Continuous $\ell$ length random walk samples from sources nodes presented adversarially or randomly.\\ 
\textbf{Source nodes $S$:} The source node of each walk of length $\ell$ can be presented adversarially or randomly accordingly to some distribution. Let this continuous sequence of source nodes be denoted by ordered set $S$.
\begin{algorithmic}[1]

\STATE Call {\sc Pre-Processing($\eta=1$, $\lambda = 24\sqrt{\ell D} (\log{n})^3$)}

\WHILE{Indefinitely}

\WHILE{Algorithm does not fail (algorithm gets stuck due to insufficient short walks)}

\STATE Select the next source node $s$ from the ordered set $S$. 

\STATE call {\sc Single-Random-Walk($s$, $\ell$)}.
%(cf. Algorithm~\ref{alg:single-random-walk})

\STATE If Single-Random-Walk returns with fail, exit loop

\ENDWHILE

\STATE Call {\sc Pre-Processing($\eta=1$, $\lambda = 24\sqrt{\ell D} (\log{n})^3$)} again and use this table.

\STATE Rerun request for $s$ and then continue subsequent walks based on random samples. 

\ENDWHILE

\end{algorithmic}

\end{algorithm}


